package org.example.myleet.p396;

public class Solution {
    public int maxRotateFunction(int[] nums) {
        //求nums的和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //求F0
        int f = 0, n = nums.length;
        for (int i = 0; i < n; ++i) {
            f += i * nums[i];
        }
        int maxF = f;
        //根据题意，可以归纳为Fn = Fn-1 + sum - n * nums[n - i];
        //此处为动态规划的思路，即下一步可以由上一步以O(1)的复杂度求出
        for (int i = 1; i < n; ++i) {
            f = f + sum - n * nums[n - i];
            maxF = Math.max(maxF, f);
        }
        return maxF;
    }
}
